Crate crypto_bigint
source ·Expand description
RustCrypto: Cryptographic Big Integers
Pure Rust implementation of a big integer library which has been designed from the ground-up for use in cryptographic applications.
Provides constant-time, no_std
-friendly implementations of modern formulas
using const generics.
Goals
- Supports
no_std
-friendly const generic stack-allocated big integers. - Constant-time by default. Variable-time functions are explicitly marked as such.
- Leverage what is possible today with const generics on
stable
rust. - Support
const fn
as much as possible, including decoding big integers from bytes/hex and performing arithmetic operations on them, with the goal of being able to compute values at compile-time.
Security Notes
This crate has been audited by NCC Group with no significant findings. We would like to thank Entropy for funding the audit.
All functions contained in the crate are designed to execute in constant
time unless explicitly specified otherwise (via a *_vartime
name suffix).
This library is not suitable for use on processors with a variable-time multiplication operation (e.g. short circuit on multiply-by-zero / multiply-by-one, such as certain 32-bit PowerPC CPUs and some non-ARM microcontrollers).
Minimum Supported Rust Version
This crate requires Rust 1.65 at a minimum.
We may change the MSRV in the future, but it will be accompanied by a minor version bump.
License
Licensed under either of:
at your option.
Contribution
Unless you explicitly state otherwise, any contribution intentionally submitted for inclusion in the work by you, as defined in the Apache-2.0 license, shall be dual licensed as above, without any additional terms or conditions.
Usage
This crate defines a Uint
type which is const generic around an inner
Limb
array, where a Limb
is a newtype for a word-sized integer.
Thus large integers are represented as arrays of smaller integers which
are sized appropriately for the CPU, giving us some assurances of how
arithmetic operations over those smaller integers will behave.
To obtain appropriately sized integers regardless of what a given CPU’s
word size happens to be, a number of portable type aliases are provided for
integer sizes commonly used in cryptography, for example:
U128
, U384
, U256
, U2048
, U3072
, U4096
.
const fn
usage
The Uint
type provides a number of const fn
inherent methods which
can be used for initializing and performing arithmetic on big integers in
const contexts:
use crypto_bigint::U256;
// Parse a constant from a big endian hexadecimal string.
pub const MODULUS: U256 =
U256::from_be_hex("ffffffff00000000ffffffffffffffffbce6faada7179e84f3b9cac2fc632551");
// Compute `MODULUS` shifted right by 1 at compile time
pub const MODULUS_SHR1: U256 = MODULUS.shr_vartime(1);
Note that large constant computations may accidentally trigger a the const_eval_limit
of the compiler.
The current way to deal with this problem is to either simplify this computation,
or increase the compiler’s limit (currently a nightly feature).
One can completely remove the compiler’s limit using:
#![feature(const_eval_limit)]
#![const_eval_limit = "0"]
Trait-based usage
The Uint
type itself does not implement the standard arithmetic traits
such as Add
, Sub
, Mul
, and Div
.
To use these traits you must first pick a wrapper type which determines
overflow behavior: Wrapping
or Checked
.
Wrapping arithmetic
use crypto_bigint::{U256, Wrapping};
let a = Wrapping(U256::MAX);
let b = Wrapping(U256::ONE);
let c = a + b;
// `MAX` + 1 wraps back around to zero
assert_eq!(c.0, U256::ZERO);
Checked arithmetic
use crypto_bigint::{U256, Checked};
let a = Checked::new(U256::ONE);
let b = Checked::new(U256::from(2u8));
let c = a + b;
assert_eq!(c.0.unwrap(), U256::from(3u8))
Modular arithmetic
This library has initial support for modular arithmetic in the form of the
AddMod
, SubMod
, NegMod
, and MulMod
traits, as well as the
support for the Rem
trait when used with a NonZero
operand.
use crypto_bigint::{AddMod, U256};
// mod 3
let modulus = U256::from(3u8);
// 1 + 1 mod 3 = 2
let a = U256::ONE.add_mod(&U256::ONE, &modulus);
assert_eq!(a, U256::from(2u8));
// 2 + 1 mod 3 = 0
let b = a.add_mod(&U256::ONE, &modulus);
assert_eq!(b, U256::ZERO);
It also supports modular arithmetic over constant moduli using Residue
,
and over moduli set at runtime using DynResidue
.
That includes modular exponentiation and multiplicative inverses.
These features are described in the modular
module.
Random number generation
When the rand_core
or rand
features of this crate are enabled, it’s
possible to generate random numbers using any CSRNG by using the
Random
trait:
use crypto_bigint::{Random, U256, rand_core::OsRng};
let n = U256::random(&mut OsRng);
Modular random number generation
The RandomMod
trait supports generating random numbers with a uniform
distribution around a given NonZero
modulus.
use crypto_bigint::{NonZero, RandomMod, U256, rand_core::OsRng};
let modulus = NonZero::new(U256::from(3u8)).unwrap();
let n = U256::random_mod(&mut OsRng, &modulus);
Re-exports
pub use subtle;
pub use generic_array;
pub use rand_core;
pub use rlp;
pub use zeroize;
Modules
- consts
generic-array
Type aliases for many constants. - Implements modular arithmetic for constant moduli.
- Import prelude for this crate: includes important traits.
Macros
- Const-friendly assertion that two values are equal.
- Const-friendly assertion that two values are NOT equal.
- Creates a
Residue
with the given value for a specific modulus. For example,residue!(U256::from(105u64), MyModulus);
creates aResidue
for 105 modMyModulus
. The modulus must be odd, or this will panic. - Implements a modulus with the given name, type, and value, in that specific order. Please
use crypto_bigint::traits::Encoding
to make this work. For example,impl_modulus!(MyModulus, U256, "73eda753299d7d483339d80809a1d80553bda402fffe5bfeffffffff00000001");
implements a 256-bit modulus namedMyModulus
. The modulus must be odd, or this will panic. - Calculate the number of limbs required to represent the given number of bits.
Structs
- BoxedUint
alloc
Fixed-precision heap-allocated big unsigned integer. - Provides intentionally-checked arithmetic on
T
. - A boolean value returned by constant-time
const fn
s. - Big integers are represented as an array of smaller CPU word-size integers called “limbs”.
- Wrapper type for non-zero integers.
- A pre-calculated reciprocal for division by a single limb.
- Stack-allocated big unsigned integer.
- Provides intentionally-wrapped arithmetic on
T
.
Traits
- Compute
self + rhs mod p
. - ArrayDecoding
generic-array
Support for decoding aGenericArray
as a big integer. - ArrayEncoding
generic-array
Support for encoding a big integer as aGenericArray
. - Integers whose representation takes a bounded amount of space.
- Checked addition.
- Checked multiplication.
- Checked subtraction.
- Concatenate two numbers into a “wide” double-width value, using the
lo
value as the least significant value. - Concatenate two numbers into a “wide” combined-width value, using the
lo
value as the least significant value. - Encoding support.
- Integer type.
- Constant-time inversion.
- Compute
self * rhs mod p
. - Performs modular multi-exponentiation using Montgomery’s ladder.
- Performs modular multi-exponentiation using Montgomery’s ladder.
exponent_bits
represents the number of bits to take into account for the exponent. - Compute
-self mod p
. - Constant-time exponentiation.
- Constant-time exponentiation with exponent of a bounded bit size.
- Random
rand_core
Random number generation support. - RandomMod
rand_core
Modular random number generation support. - Split a number in half, returning the most significant half followed by the least significant.
- Split a number into parts, returning the most significant part followed by the least significant.
- Support for optimized squaring
- Compute
self - rhs mod p
. - Zero values.
Type Aliases
- ByteArray
generic-array
Alias for a byte array whose size is defined byArrayEncoding::ByteSize
. - 64-bit unsigned big integer.
- 128-bit unsigned big integer.
- 192-bit unsigned big integer.
- 256-bit unsigned big integer.
- 320-bit unsigned big integer.
- 384-bit unsigned big integer.
- 448-bit unsigned big integer.
- 512-bit unsigned big integer.
- 576-bit unsigned big integer.
- 640-bit unsigned big integer.
- 704-bit unsigned big integer.
- 768-bit unsigned big integer.
- 832-bit unsigned big integer.
- 896-bit unsigned big integer.
- 960-bit unsigned big integer.
- 1024-bit unsigned big integer.
- U1088
extra-sizes
1088-bit unsigned big integer. - U1152
extra-sizes
1152-bit unsigned big integer. - U1216
extra-sizes
1216-bit unsigned big integer. - 1280-bit unsigned big integer.
- U1344
extra-sizes
1344-bit unsigned big integer. - U1408
extra-sizes
1408-bit unsigned big integer. - U1472
extra-sizes
1472-bit unsigned big integer. - 1536-bit unsigned big integer.
- U1600
extra-sizes
1600-bit unsigned big integer. - U1664
extra-sizes
1664-bit unsigned big integer. - U1728
extra-sizes
1728-bit unsigned big integer. - 1792-bit unsigned big integer.
- U1856
extra-sizes
1856-bit unsigned big integer. - U1920
extra-sizes
1920-bit unsigned big integer. - U1984
extra-sizes
1984-bit unsigned big integer. - 2048-bit unsigned big integer.
- U2112
extra-sizes
2112-bit unsigned big integer. - U2176
extra-sizes
2176-bit unsigned big integer. - U2240
extra-sizes
2240-bit unsigned big integer. - U2304
extra-sizes
2304-bit unsigned big integer. - U2368
extra-sizes
2368-bit unsigned big integer. - U2432
extra-sizes
2432-bit unsigned big integer. - U2496
extra-sizes
2496-bit unsigned big integer. - U2560
extra-sizes
2560-bit unsigned big integer. - U2624
extra-sizes
2624-bit unsigned big integer. - U2688
extra-sizes
2688-bit unsigned big integer. - U2752
extra-sizes
2752-bit unsigned big integer. - U2816
extra-sizes
2816-bit unsigned big integer. - U2880
extra-sizes
2880-bit unsigned big integer. - U2944
extra-sizes
2944-bit unsigned big integer. - U3008
extra-sizes
3008-bit unsigned big integer. - 3072-bit unsigned big integer.
- U3136
extra-sizes
3136-bit unsigned big integer. - U3200
extra-sizes
3200-bit unsigned big integer. - U3264
extra-sizes
3264-bit unsigned big integer. - U3328
extra-sizes
3328-bit unsigned big integer. - U3392
extra-sizes
3392-bit unsigned big integer. - U3456
extra-sizes
3456-bit unsigned big integer. - U3520
extra-sizes
3520-bit unsigned big integer. - 3584-bit unsigned big integer.
- U3648
extra-sizes
3648-bit unsigned big integer. - U3712
extra-sizes
3712-bit unsigned big integer. - U3776
extra-sizes
3776-bit unsigned big integer. - U3840
extra-sizes
3840-bit unsigned big integer. - U3904
extra-sizes
3904-bit unsigned big integer. - U3968
extra-sizes
3968-bit unsigned big integer. - U4032
extra-sizes
4032-bit unsigned big integer. - 4096-bit unsigned big integer.
- U4160
extra-sizes
4160-bit unsigned big integer. - 4224-bit unsigned big integer.
- U4288
extra-sizes
4288-bit unsigned big integer. - 4352-bit unsigned big integer.
- U4416
extra-sizes
4416-bit unsigned big integer. - U4480
extra-sizes
4480-bit unsigned big integer. - U4544
extra-sizes
4544-bit unsigned big integer. - U4608
extra-sizes
4608-bit unsigned big integer. - U4672
extra-sizes
4672-bit unsigned big integer. - U4736
extra-sizes
4736-bit unsigned big integer. - U4800
extra-sizes
4800-bit unsigned big integer. - U4864
extra-sizes
4864-bit unsigned big integer. - U4928
extra-sizes
4928-bit unsigned big integer. - U4992
extra-sizes
4992-bit unsigned big integer. - U5056
extra-sizes
5056-bit unsigned big integer. - U5120
extra-sizes
5120-bit unsigned big integer. - U5184
extra-sizes
5184-bit unsigned big integer. - U5248
extra-sizes
5248-bit unsigned big integer. - U5312
extra-sizes
5312-bit unsigned big integer. - U5376
extra-sizes
5376-bit unsigned big integer. - U5440
extra-sizes
5440-bit unsigned big integer. - U5504
extra-sizes
5504-bit unsigned big integer. - U5568
extra-sizes
5568-bit unsigned big integer. - U5632
extra-sizes
5632-bit unsigned big integer. - U5696
extra-sizes
5696-bit unsigned big integer. - U5760
extra-sizes
5760-bit unsigned big integer. - U5824
extra-sizes
5824-bit unsigned big integer. - U5888
extra-sizes
5888-bit unsigned big integer. - U5952
extra-sizes
5952-bit unsigned big integer. - U6016
extra-sizes
6016-bit unsigned big integer. - U6080
extra-sizes
6080-bit unsigned big integer. - 6144-bit unsigned big integer.
- U6208
extra-sizes
6208-bit unsigned big integer. - U6272
extra-sizes
6272-bit unsigned big integer. - U6336
extra-sizes
6336-bit unsigned big integer. - U6400
extra-sizes
6400-bit unsigned big integer. - U6464
extra-sizes
6464-bit unsigned big integer. - U6528
extra-sizes
6528-bit unsigned big integer. - U6592
extra-sizes
6592-bit unsigned big integer. - U6656
extra-sizes
6656-bit unsigned big integer. - U6720
extra-sizes
6720-bit unsigned big integer. - U6784
extra-sizes
6784-bit unsigned big integer. - U6848
extra-sizes
6848-bit unsigned big integer. - U6912
extra-sizes
6912-bit unsigned big integer. - U6976
extra-sizes
6976-bit unsigned big integer. - U7040
extra-sizes
7040-bit unsigned big integer. - U7104
extra-sizes
7104-bit unsigned big integer. - U7168
extra-sizes
7168-bit unsigned big integer. - U7232
extra-sizes
7232-bit unsigned big integer. - U7296
extra-sizes
7296-bit unsigned big integer. - U7360
extra-sizes
7360-bit unsigned big integer. - U7424
extra-sizes
7424-bit unsigned big integer. - U7488
extra-sizes
7488-bit unsigned big integer. - U7552
extra-sizes
7552-bit unsigned big integer. - U7616
extra-sizes
7616-bit unsigned big integer. - U7680
extra-sizes
7680-bit unsigned big integer. - U7744
extra-sizes
7744-bit unsigned big integer. - U7808
extra-sizes
7808-bit unsigned big integer. - U7872
extra-sizes
7872-bit unsigned big integer. - U7936
extra-sizes
7936-bit unsigned big integer. - U8000
extra-sizes
8000-bit unsigned big integer. - U8064
extra-sizes
8064-bit unsigned big integer. - U8128
extra-sizes
8128-bit unsigned big integer. - 8192-bit unsigned big integer.
- 16384-bit unsigned big integer.
- 32768-bit unsigned big integer.
- WideWord64-bitWide integer type: double the width of
Word
. - Word64-bitUnsigned integer type that the
Limb
newtype wraps.